﻿//394. 字符串解码
//给定一个经过编码的字符串，返回它解码后的字符串。
//编码规则为 : k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
//你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
//此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。


class Solution {
public:


    string getnum(string& s, int& ptr) {
        string ret = "";
        while (isdigit(s[ptr])) {
            ret.push_back(s[ptr++]);
        }
        return ret;
    }

    string getString(vector <string>& v) {
        string ret;
        for (const auto& s : v) {
            ret += s;
        }
        return ret;
    }

    string decodeString(string s)
    {
        vector<string> sta;
        int i = 0;
        int n = s.size();
        while (i < n)
        {
            char cur = s[i];
            if (isdigit(cur))
            {
                //获取数字
                string num = getnum(s, i);
                sta.push_back(num);
            }
            else if (isalpha(cur) || cur == '[')
            {
                sta.push_back(string(1, s[i++]));
            }
            else
            {
                i++;
                vector<string> sub;
                while (sta.back() != "[")
                {
                    sub.push_back(sta.back());
                    sta.pop_back();
                }
                reverse(sub.begin(), sub.end());
                sta.pop_back();
                int time = stoi(sta.back());
                sta.pop_back();
                string t, o = getString(sub);
                // 构造字符串
                while (time--) t += o;
                sta.push_back(t);
            }
        }
        return getString(sta);
    }
};